1. Field of the Invention
The present invention relates to the field of data processing systems. Specifically, the present invention relates to a method and system for encoding information in a portable computer system.
2. Related Art
As the components required to build a computer system have reduced in size, new categories of computer systems have emerged. One of the more recent categories of computer systems is the xe2x80x9cpalmtopxe2x80x9d computer system. A palmtop computer system is a computer that is small enough to be held in the hand of a user and is thus xe2x80x9cpalm-sized.xe2x80x9d
Because palmtop computer systems are very small, full-sized keyboards are generally not efficient input devices. Instead of a keyboard device, some palmtop computers utilize a touch screen and display an image of a small keyboard thereon. When a particular button is pressed or tapped, a small keyboard image is displayed on the display screen. The user then interacts with the on-screen small keyboard image to enter characters, usually one character at a time. To interact with the displayed keyboard image (e.g., xe2x80x9cvirtual keyboardxe2x80x9d), the user taps the screen location of a character with a pen. That corresponding character is then recognized and added to a data entry field, also displayed on the screen. However, for experienced users, the virtual keyboard input system can be a tedious input process.
Instead of using a keyboard device or a displayed keyboard, many palmtop computers employ a stylus and a digitizer pad as an input system. The pen and digitizer pad combination works well for palmtop computers because the arrangement allows a user to hold the palmtop computer system in one hand while scribing with the stylus onto the digitizer pad with the other hand. Most of these stylus-based palmtop computer systems provide some type of handwriting recognition system.
In addition to using keyboards, virtual keyboards and the digitizer, it has also proven convenient to exchange data between a computer system and a palmtop computer using a communication interface, such as a serial or parallel input port. Many palmtop computers also include an infrared communication port for transmitting data over a wireless link. Other palmtop computers further include a radio receiver/transmitter for transmitting data over a wireless link.
All communication circuits introduce some noise and interference into a signal, whether the signal is analog or digital. In addition, signals are distorted along their transmission path by noise and interference. The noise and interference add elements (errors) to the signals that need to be considered in order to recover the original signal.
Error correcting codes are known in the art and are used to encode and decode a signal in such a way that noise and interference errors can be detected and corrected by examination of the encoded data on the receiving end. In a forward error correcting code, extra (redundant) bits (xe2x80x9cparity bitsxe2x80x9d) are added into a stream of data that is to be transmitted to another device. The parity bits are used by the receiving device to detect and correct errors in the received data.
In a block error correcting code, a block of K digits (e.g., a data word) is encoded using a code word of N digits (where N greater than K). For each sequence of K digits, there is a distinct code word of N digits. The code word is comprised of K data bits and N-K parity bits. Generally, such a code is known as a (N,K) code; certain types of these codes are also called Hamming codes. A total of 2K code words having N digits each is required for 2K data words. Thus, for example, for a data word that is eight (8) bits in length, 256 code words are required.
A typical encoding scheme of the prior art is generalized as mapping K-bit vectors X into N-bit vectors Y using a generator G specific to the code being used, in which:
[Y]=[X][G].
Thus, for example, if K=8 and N=12, then:
[Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12]=[X1X2X3X4X5X6X7X8][G].
In this example, [Y] would have 8 data bits (X) and 4 parity bits (P):
[Y]=[X1X2X3X4X5X6X7X8P1P2P3P4].
Once G has been selected, the encoding scheme can be executed in advance for each possible combination of K bits, and the encoded results stored in a lookup table. Accordingly, to encode a K-bit data word, the data word is used as an index into the lookup table to identify the corresponding N-bit code word previously determined using generator G. For K=8 and N=12, for example, the lookup table will have 256 12-bit entries. Table 1 below is an example of such a lookup table.
A problem with this prior art approach is that the lookup tables are large in size and therefore require a large amount of memory. For longer data words and/or code words, this problem is made even worse. For example, increasing the size of the data word by one bit (from 8 bits to 9) doubles the number of entries required in the lookup table, from 256 entries to 512; each additional bit in the data word doubles the size of the lookup table.
In a palmtop computer system, the amount of memory space is limited relative to desktop computer systems (e.g., personal computers), and therefore memory space is invaluable and needs to be efficiently used. In addition, it may take longer to complete the encoding and decoding processes using large lookup tables.
Consumer preferences are for palmtops and other such devices to be as small, light and fast as possible. As such, it is desirable to use the memory space available, as well as to perform necessary functions such as encoding and decoding, as efficiently as possible.
Accordingly, what is needed is a system or method for efficiently encoding and decoding a digital data stream in accordance with the limited resources available in palmtop computer systems and other small, low-power devices. In particular, what is needed is a system or method that satisfies the above need and that does not consume a large amount of the available memory space in such devices. The present invention provides these advantages and others not specifically mentioned above but described in the sections to follow.
A method and system are described for encoding and decoding a sequence of K binary digits using reduced-size lookup tables. In the present embodiment, the sequence of K binary digits is separated into multiple segments (for example, a first segment and a second segment), The first segment is used as an index into a first lookup table that contains an encoded sequence corresponding to each of the possible combinations of binary digits in the first segment. Similarly, the second segment is used as an index into a second lookup table that contains an encoded sequence corresponding to each of the possible combinations of binary digits in the second segment. Using the first lookup table, an encoded sequence is obtained for the first segment, and an encoded sequence is obtained for the second segment using the second lookup table. An encoded sequence for the entire sequence of K binary digits is obtained by combining the encoded sequences for the first and second segments.
In other embodiments, the K binary digits are separated into more than two segments. Accordingly, in these embodiments, more than two lookup tables are used to encode the K binary digits in a manner similar to that just described.
Hence, in accordance with the present invention, instead of a single lookup table with 2K entries, multiple reduced-size lookup tables are used to encode a sequence of K binary digits. The total number of entries in the reduced-size lookup tables is less than 2K entries, thereby saving memory space in devices with limited memory capacity, such as palmtop computers.
In the present embodiment, an error correcting code is used to generate the encoded sequences that are stored in the reduced-size lookup tables. In one embodiment, the error correcting code is a Hamming code.
In one embodiment, the encoded sequences for the first and second segments are combined using a binary add XOR (exclusive or) operation.
In another embodiment, the sequence of K binary digits to be encoded are substantially compliant with the Mobitex standard.